#include "ReduceColor.h"

using namespace std;

void ReduceColor::MCAReduce(ColorSet &in,
                            const list<Color> &extraColor,
                            Palette &out, unordered_map<Color, uint32_t> &colorMap)
{
    auto inList = in.ToList();
    list<list<tuple<Color, int32_t>>> inSet;
    // 讲需要划分的颜色集合作为一个整体传入inSet
    inSet.emplace_back(inList);
    // 讲额外的颜色(如所属色之类)作为单个颜色传入inSet, inSet中单个颜色不可再被划分
    for (auto& i : extraColor)
        inSet.emplace_back(list{tuple(i, 0)});
    // 若inSet的大小不足256, 则反复划分inSet
    while (inSet.size() < 256)
    {
        auto iter = inSet.end();
        // 从inSet中找到最需要被划分的颜色集合
        if (!MCAUtil::GetNextSet2Cut(inSet, iter))
            break;
        list<tuple<Color, int32_t>> l1, l2;
        // 将找到的颜色集合中位划分为两个颜色集合, 每个集合中包含的颜色种数相同
        MCAUtil::Cut(*iter, l1, l2);
        // 从inSet中删除原颜色集合并加入划分后的集合
        inSet.erase(iter);
        inSet.emplace_back(l1);
        inSet.emplace_back(l2);
    }

    // 从inSet每个集合中提取平均颜色作为该集合的提取颜色, 添加到传出的map, 并且将该集合内的颜色提取到色彩映射表中.
    size_t order = 0;
    for (auto &i : inSet)
    {
        uint64_t r = 0;
        uint64_t g = 0;
        uint64_t b = 0;
        uint64_t a = 0;
        for (auto &j : i)
        {
            auto c = get<0>(j);
            r += c.r;
            g += c.g;
            b += c.b;
            a += c.a;
            colorMap.insert(make_pair(c, order));
        }
        out[order] = Color(r / i.size(), g / i.size(), b / i.size(), a / i.size());
        order++;
    }
}


bool ReduceColor::MCAUtil::GetNextSet2Cut(list<std::list<std::tuple<Color, int32_t>>> &in,
                                          list<list<std::tuple<Color, int32_t>>>::iterator &out)
{

    list<tuple<list<list<tuple<Color, int32_t>>>::iterator , int>> counterMap;
    for(auto i = in.begin(); i != in.end(); i++)
    {
        if (i->size() < 2) {
            counterMap.emplace_back(tuple(i, 0));
            continue;
        }
        int counter = 0;
        for (const auto& j : *i)
            counter += get<1>(j);
        counterMap.emplace_back(tuple(i, counter));
    }
    counterMap.sort([](const tuple<list<list<tuple<Color, int32_t>>>::iterator , int>& a,
                       const tuple<list<list<tuple<Color, int32_t>>>::iterator , int>& b)->bool{
        return get<1>(a) > get<1>(b);
    });
    if (get<1>(*(counterMap.begin())) != 0)
    {
        out = get<0>(*(counterMap.begin()));
        return true;
    }
    else
    {
        out = in.end();
        return false;
    }
}

bool ReduceColor::MCAUtil::Cut(list<std::tuple<Color, int32_t>> &in,
                               list<std::tuple<Color, int32_t>> &out1,
                               list<std::tuple<Color, int32_t>> &out2)
{
    uint64_t r0 = get<0>(*in.begin()).r, r1 = r0;
    uint64_t g0 = get<0>(*in.begin()).g, g1 = g0;
    uint64_t b0 = get<0>(*in.begin()).b, b1 = b0;
    uint64_t a0 = get<0>(*in.begin()).a, a1 = a0;
    for (auto &i : in)
    {
        const auto& c = get<0>(i);
        if (c.r < r0) r0 = c.r;
        if (c.r > r1) r1 = c.r;
        if (c.g < g0) g0 = c.g;
        if (c.g > g1) g1 = c.g;
        if (c.b < b0) b0 = c.b;
        if (c.b > b1) b1 = c.b;
        if (c.a < a0) a0 = c.a;
        if (c.a > a1) a1 = c.a;
    }
    uint64_t dr = r1 - r0;
    uint64_t dg = g1 - g0;
    uint64_t db = b1 - b0;
    uint64_t da = a1 - a0;
    uint64_t maxD = max({dr, dg, db, da});
    if (dr == maxD)
        in.sort([](const tuple<Color, int32_t>& c1, const tuple<Color, int32_t>& c2)->bool{
            return get<0>(c1).r > get<0>(c2).r;
        });
    else if (dg == maxD)
        in.sort([](const tuple<Color, int32_t>& c1, const tuple<Color, int32_t>& c2)->bool{
            return get<0>(c1).g > get<0>(c2).g;
        });
    else if (db == maxD)
        in.sort([](const tuple<Color, int32_t>& c1, const tuple<Color, int32_t>& c2)->bool{
            return get<0>(c1).b > get<0>(c2).b;
        });
    else if (da == maxD)
        in.sort([](const tuple<Color, int32_t>& c1, const tuple<Color, int32_t>& c2)->bool{
            return get<0>(c1).a > get<0>(c2).a;
        });
    auto iter = in.begin();
    for (int i = 0; i < in.size() / 2; i++)
        iter++;
    auto l1 = list<tuple<Color, int32_t>>(in.begin(), iter);
    auto l2 = list<tuple<Color, int32_t>>(iter, in.end());
    out1.swap(l1);
    out2.swap(l2);
    return true;
}
